/**
 * 插入排序
 */
public class InsertionSort {

    // 对选择排序进一步优化，向左侧有序数组插入元素
    // 改算法又名插入排序
    public void sort(int[] nums) {
        int n = nums.length;
        // 维护[0, sortedIndex)为有序区间
        int sortedIndex = 0;
        while (sortedIndex < n) {
            // 将nums[sortedIndex]插入到左侧有序数组中
            for (int i = sortedIndex; i > 0; i--) {
                if (nums[i] < nums[i - 1]) {
                    int temp = nums[i];
                    nums[i] = nums[i - 1];
                    nums[i - 1] = temp;
                } else {
                    break;
                }
            }
            sortedIndex++;
        }
    }
}
